The present invention is used for routes designing of an integrated circuit. In particular, the invention relates to a routes designing scheme which is used for a channel routing region having routing prohibition figures that are existing interconnections and circuit parts already disposed in channel routing in a detailed routing process of layout design.
In layout design of an integrated circuit, for such purposes as minimization of the area occupied by interconnections by tapering power lines and clock skew reduction of clock lines, these kinds of special lines are usually routed prior to routing of ordinary signal lines. In this case, prerouted special lines exist in a channel routing region as existing interconnections and need to be handled as routing prohibition figures (obstacles) in routing ordinary signal lines. In assigning trunks (horizontal interconnections) of ordinary signal line nets to a channel routing region, it is necessary to assign the trunks so as to avoid routing prohibition figures.
Most of conventional routing methods are applicable only with an assumption of a routing model that no obstacles exist within a subject routing region, and hence cannot be applied to a channel routing region having routing prohibition figures.
An automatic routing scheme disclosed in Japanese Unexamined Patent Publication No. Hei. 4-167073 is adapted to be applicable to even a routing region having routing prohibition figures. In this routing scheme, net trunks are assigned to a channel routing region according to a routing flow shown in FIG. 1. This routing scheme cannot assign trunks to a net having terminals on both of a top cell row and a bottom cell row within the range of a routing prohibition figure (i.e., between the left end and the right end of the figure). This will be explained below by using examples.
In a channel routing region shown in FIG. 2, a consideration will be given to net n for connecting terminal t1 on a top cell row and terminal t2 on a bottom cell row of the channel routing region. Both terminals t1 and t2 exist within the range of a routing prohibition figure (intrachannel obstacle) R. Four routing tracks T1-T4 are disposed between a top boundary 11 and a bottom boundary 12.
First, at steps S101 and S102, a position constraint graph representing a vertical constraint relationship among trunks is generated. Nodes correspond to trunks or obstacles. Directed branch (a, b) represents a constraint that trunk a (or obstacle a) must be assigned to a routing track above trunk b (or obstacle b). As shown in FIG. 3, a position constraint graph of the channel routing region of FIG. 2 has a cycle including node R which corresponds to the intrachannel obstacle R and node n which corresponds to a trunk of net n.
Then, at step S103, weights are given to the respective nodes. Each node n representing a trunk of the net is given a weight 1. Node R representing the obstacle is given a weight equal to the number of tracks that are prevented by the obstacle from being assigned a trunk. In this case, node R is given a weight 2.
At step S104, among the nodes u in the position constraint graph a node that no directed branch enters is considered a start node, and an accumulation value of weights of all nodes existing on an arrowed route from the start point to node u is made a rank of node u. Since the position constraint graph of FIG. 3 is in cycle form, the rank of node n cannot be determined. Thus, if a position constraint graph representing a vertical constraint of a channel routing region has a cycle including an obstacle and a trunk, the channel routing method under consideration cannot be applied thereto.
Assume a case in which an intrachannel routing prohibition figure (obstacle) V shown in FIG. 4 is an obstacle to a wiring layer M1 (FIG. 6) for routing trunks (horizontal interconnections) but not an obstacle to a wiring layer M2 (FIG. 6) for routing branches (vertical interconnections) that connect trunks and terminals. An obstacle R obstructs both types of wiring layers for trunks and branches. The number of tracks that are prevented by the obstacle V from being assigned a trunk is 2. In two nets n1={t1, t3} and n2={t2, t4}, terminal t1 of net n1 is located over the obstacle V and terminal t4 of net n2 is located under the obstacle R. No vertical constraint exists between trunks of nets n1 and n2. In this case, a position constraint graph generated by steps S101 and S102 is a directed graph shown in FIG. 5, where nodes corresponding to the obstacles V and R and nets n1 and n2 are denoted by V and R and n1 and n2, respectively. At step S103, node V is given a weight 2 and the other three nodes are given a weight 1. At step S104, the rank of node n2 is calculated as 2 because there is a directed branch from node R to node n2. On the other hand, the rank of node nl is calculated as 1. Therefore, at step S106, a trunk of net n2 corresponding to node n2 is assigned to the lowest track T3. The process is finished in a state that a trunk of net n1 corresponding to node n1 is not assigned to any track. Thus, net n1 cannot be routed as shown in FIG. 6.
Japanese Unexamined Patent Publication No. Hei. 8-274179 discloses a routing scheme which can determine routes on even the channel routing regions of FIGS. 2 and 4. Net trunks are assigned to a channel routing region according to a routing flow shown in FIG. 7. In this routing scheme, a subchannel region that is not obstructed by any routing prohibition figures is set in the channel routing region. Trunks are assigned to tracks in the region such that as the routing process proceeds the subchannel regions are updated for a region excluding already assigned trunks and routing prohibition figures. In this routing scheme, the shape of subchannel regions that is formed during the routing process is determined by the positions of routing prohibition figures in the channel routing region and assigned net trunks. Therefore, there may occur a case that net trunks cannot be assigned for a routable channel routing region. This will be described below by using an example.
In a channel routing region shown in FIG. 8A, terminals t1 and t2 exist on a top cell row and terminals t3 and t4 exist on a bottom cell row of the channel routing region. It is assumed that two wiring layers M1 and M2 are used for the routing and the M1 layer and the M2 layer are used for the horizontal direction and the vertical direction, respectively. Terminal t1 is located over a routing prohibition figure V1, terminal t2 is located over a routing prohibition figure V3, and terminal t4 is located under a routing prohibition figure V5. Terminal t3 exists on a column where no routing prohibition figure exists. All of routing prohibition figures V1-V5 in the routing region serve as routing prohibition figures for the wiring layer M1 (used for the horizontal routing). A consideration will be given to net n1 for connecting terminals t1 and t4 and net n2 for connecting terminals t2 and t3.
First, referring to FIG. 7, at steps S201 and S202, a subchannel for the wiring layer M1 (used for the horizontal routing) is set as shown in FIG. 8A.
Then, at step S203, temporary terminals are provided on the boundary lines of the subchannel for the respective terminals belonging to nets n1 and n2 (see FIG. 8B).
At step S204, a set S of candidate nets to be routed in the subchannel is {n1, n2}.
Then, at step S205, since terminal t2 of net n2 is located over terminal t4 of net n1, according to a vertical constraint a trunk of net n2 should be assigned to a track above a track to which a trunk of net n1 is assigned. Therefore, a trunk of net n2 is assigned to track T2.
At steps S206 and S207, the routing prohibition figures are updated based on the routing of the net whose trunk has been assigned at step S205, and the assigning-completed net is deleted from the net list.
At step S208, since the net list includes only net n1 but is not an empty set, steps S202-S208 are repeated.
In the second loop of steps S202-S208, a subchannel and temporary terminals of net n1 are set as shown in FIG. 8C. It appears that a trunk of net n1 can be assigned to track T4. However, track T4 does not include an interval having terminals t1 and t4 as the left and right ends, respectively. Thus, actually a trunk of net n1 cannot be assigned to track T4, and net n1 remains unrouted.
Integrated circuit routes designing is theoretically discussed in the following papers.
(1) 17th ACM/IEEE Design Automation Conference (1980), pages 32-39, under the title of "AN OVER-THE-CELL-ROUTER" by David N. Deutsch and another.
(2) 20th ACM/IEEE Design Automation Conference (1983), pages 665-670, under the title of "AN OVER-CELL GATE ARRAY CHANNEL ROUTER" by Howard E. Krohn.
(3) IEEE Transactions on Computer-Aided Design, Vol. CAD-6, No.3 (May 1987), pages 462-471, under the title of "A Permeation Router" by Y. Shiraishi and another.
(4) ICCAD IEEE (1988), pages 80-83, under the title of "Over-the-Cell Channel Routing" by J. Cong and another.
(5) 27th ACM/IEEE Design Automation Conference (1990), pages 709-715, under the title of "GENERAL MODELS AND ALGORITHMS FOR OVER-THE-CELL-ROUTING IN STANDARD CELL DESIGN" by J. Cong and two others.
(6) 28th ACM/IEEE Design Automation Conference (1991), pages 120-125, under the title of "Channel Density Reduction By Routing Over The Cells" by Min-Siang Lin and three others.
(7) 28th ACM/IEEE Design Automation Conference (1991), pages 126-131, under the title of "New Algorithm for Over-the-Cell Channel Routing Using Vacant Terminals" by Nancy D. Holmes and two others.
(8) VLSI 91, pages 8a.2.1-8a.2.10, under the title of "An Over-the-cell Channel Router" by Ravi R. Pal and another.
(9) ICCAD IEEE (1991), pages 428-431, under the title of "Algorithms for Three-Layer Over-the-Cell Channel Routing" by Nancy D. Holmes and two others.
(10) ICCAD IEEE (1991), pages 432-435, under the title of "A New Model for Over-the-Cell Channel Routing with Three Layers" by M. Terai and three others.
(11) 29th ACM/IEEE Design Automation Conference (1992), pages 585-588, under the title of "A Multi-Layer Channel Router with New Style of Over-the-Cell Routing" by T. Fujii (the inventor) and three others.
(12) 29th ACM/IEEE Design Automation Conference (1992), pages 600-603, under the title of "Over-the-Cell Channel Routing For High Performance Circuits" by S. Natarajan and three others.
(13) 29th ACM/IEEE Design Automation Conference (1992), pages 604-607, under the title of "Over-the-Cell Routers for New Cell Model" by Bo Wu, Naveed A. Sherwani and two others.
(14) VLSI 93, pages 8.1.1-8.1.10, under the title of "A Multi-Layer Channel Router Based on Optimal Multi-layer Net Assignment" by M. Sode and two others.